package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 876. 链表的中间结点
 * @since 2024/2/2 16:43
 */
public class MiddleNode876 {
    // 给你单链表的头结点 head ，请你找出并返回链表的中间结点。

    // 如果有两个中间结点，则返回第二个中间结点。
    // 解：快慢指针法
    public ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 慢指针，中间点
        ListNode p1 = head;
        // 快指针
        ListNode p2 = head;
        // 快指针走两步，慢指针走一步
        // p2 != null 应对偶数
        // p2.next != null 应对基数
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }
}
